package l10;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class BinaryTree<E> {
    private static class Node<E>{
        E data;
        Node<E> left;
        Node<E> right;
        Node(E data){
            this.data = data;
            this.left = null;
            this.right = null;
        }
        Node(E data, Node<E> left, Node<E> right){
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
    private Node<E> root;
    public BinaryTree(){
        this.root = null;
    }
    public boolean isEmpty(){
        return root == null;
    }

    public void clear(){
        clear(root);
        root =null;
    }
    private void clear(Node<E> node){
        if(node == null){
            return;
        }
        clear(node.left);
        clear(node.right);
        node = null;
    }

    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node<E> node){
        if(node == null){
            return;
        }
        System.out.print(node.data + " ");
        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(Node<E> node){
        if(node == null){
            return;
        }
        inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }

    public void postOrder(){
        postOrder(root);
    }

    private void postOrder(Node<E> node){
        if(node == null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }

    public void levelOrderTraverse(){
        if(root == null){return;}
        Queue<Node<E>> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node<E> node = queue.poll();
            System.out.print(node.data + " ");
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right != null){
                queue.add(node.right);
            }
        }
    }

    public void preOrderCreate(char flag){
        Scanner sc = new Scanner(System.in);
        System.out.println("输入带外部结点的前序遍历序列（" + flag + "表示NULL为外部结点，用空格分割字符）：");
        root = createPreOrder(flag, sc);
    }

    private Node<E> createPreOrder(char flag, Scanner scanner) {
        String token = scanner.next();
        if (token.charAt(0) == flag) return null;
        Node<E> node = new Node<>((E) Character.valueOf(token.charAt(0)));
        node.left = createPreOrder(flag, scanner);
        node.right = createPreOrder(flag, scanner);
        return node;
    }

    public int size(){
        return size(root);
    }

    private int size(Node<E> node){
        if(node == null){
            return 0;
        }
        return 1 + size(node.left) + size(node.right);
    }

    public int height(){
        return height(root);
    }

    private int height(Node<E> node){
        if(node == null){
            return 0;
        }
        int leftHeight = height(node.left);
        int rightHeight = height(node.right);
        return Math.max(leftHeight, rightHeight) + 1;
    }

    public int leafNum(){
        return leafNum(root);
    }

    private int leafNum(Node<E> node){
        if(node == null){
            return 0;
        }
        if(node.left == null&&node.right == null){
            return 1;
        }
        return leafNum(node.left) + leafNum(node.right);
    }
}

